package com.formula.datastructure.exam.sort;

import com.formula.datastructure.util.DataUtil;

public class ShellSort {
    public Integer[] sort(Integer[] array) {
        int N = array.length;
        for (int step = N / 2; step > 0; step = step / 2) {
            Integer insert;
            int idx;
            for (int i = step; i < N; i++) {
                insert = array[i];
                idx = i;
                for (int j = i - step; j > 0; j = j - step) { // 注意j是减
                    if (insert < array[j]) {
                        array[j + step] = array[j];
                        idx = j;
                    } else {
                        break; // 一定要break
                    }
                }
                if (idx != i) {
                    array[idx] = insert;
                }
            }
        }
        return array;
    }

    public static void main(String[] args) {
        ShellSort shell = new ShellSort();

        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(shell.sort(array));
    }
}
